#include <bits/stdc++.h>

using namespace std;

// 最大为N的数字组合
// 给定一个按 非递减顺序 排列的数字数组 digits
// 已知digits一定不包含'0'，可能包含'1' ~ '9'，且无重复字符
// 你可以用任意次数 digits[i] 来写的数字
// 例如，如果 digits = ['1','3','5']
// 我们可以写数字，如 '13', '551', 和 '1351315'
// 返回 可以生成的小于或等于给定整数 n 的正整数的个数
// 测试链接 : https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/

class Solution 
{
public:
    int atMostNGivenDigitSet1(vector<string>& strs, int num) 
    {
        int tmp = num / 10;
        int len = 1;
        int offset = 1;
        // 654 -> len = 3, offset = 100
        while(tmp > 0)
        {
            tmp /= 10;
            ++len;
            offset *= 10;
        }
        // 将字符串转成数字，这一步不一定要做，因为只有一位数
        int m = strs.size();
        vector<int> digits(m);
        for(int i = 0; i < m; ++i)
        {
            digits[i] = stoi(strs[i]);
        }
        return f1(digits, num, offset, len, 0, 0);
    }

	// offset是辅助变量，完全由len决定，只是为了方便提取num中某一位数字，不是关键变量
	// 还剩下len位没有决定
	// 如果之前的位已经确定比num小，那么free == 1，表示接下的数字可以自由选择
	// 如果之前的位和num一样，那么free == 0，表示接下的数字不能大于num当前位的数字
	// 如果之前的位没有使用过数字，fix == 0
	// 如果之前的位已经使用过数字，fix == 1
	// 返回最终<=num的可能性有多少种
    int f1(vector<int>& digits, int num, int offset, int len, int free, int fix)
    {
        if(len == 0) return fix == 1 ? 1 : 0;
        int ans = 0;
        // num在当前位的数字
        // num = 654, offset = 100 -> 6
        // num = 654, offset = 10 -> 5
        // num = 654, offset = 1 -> 4
        int cur = (num / offset) % 10;
        // 之前从来没有选择过数字
        // 当前依然可以不要任何数字，累加后续的可能性
        if(fix == 0) ans += f1(digits, num, offset / 10, len - 1, 1, 0);
        // 之前选择过了数字
        if(free == 0)
        {
            // 不能自由选择的情况
            for(int i : digits)
            {
                if(i < cur)
                    ans += f1(digits, num, offset / 10, len - 1, 1, 1);
                else if(i == cur)
                    ans += f1(digits, num, offset / 10, len - 1, 0, 1);
                else // i > cur，题目有交代 digits 中的数字是有序的，所以 break 即可
                    break;
            }
        }
        else
        {
            // 可以自由选择的情况
            ans += digits.size() * f1(digits, num, offset / 10, len - 1, 1, 1);
        }
        return ans;
    }


    int atMostNGivenDigitSet2(vector<string>& strs, int num) 
    {
        int tmp = num / 10;
        int len = 1;
        int offset = 1;
        // 654 -> len = 3, offset = 100
        while(tmp > 0)
        {
            tmp /= 10;
            ++len;
            offset *= 10;
        }
        // 将字符串转成数字，这一步不一定要做，因为只有一位数
        int m = strs.size();
        vector<int> digits(m);
        for(int i = 0; i < m; ++i)
        {
            digits[i] = stoi(strs[i]);
        }
        // cnt[i] : 已知前缀比num小，剩下i位没有确定，请问前缀确定的情况下，一共有多少种数字排列
		// cnt[0] = 1，表示后续已经没有了，前缀的状况都已确定，那么就是1种
		// cnt[1] = m
		// cnt[2] = m * m
		// cnt[3] = m * m * m
		// ...
        int cnt[len];
        cnt[0] = 1;
        int ans = 0;
        for(int i = m, k = 1; k < len; ++k, i *= m)
        {
            cnt[k] = i;
            ans += i;
        }
        // ans : 不够len位数的数字个数总和
        return ans + f2(digits, cnt, num, offset, len);
    }

	// offset是辅助变量，由len确定，方便提取num中某一位数字
	// 还剩下len位没有决定，之前的位和num一样
	// 返回最终<=num的可能性有多少种
    int f2(vector<int>& digits, int* cnt, int num, int offset, int len)
    {
        if(len == 0) return 1; // num自己
        // cur是num当前位的数字
        int cur = (num / offset) % 10;
        int ans = 0;
        for(int i : digits)
        {
            // cnt[i] : 已知前缀比num小，剩下i位没有确定，请问前缀确定的情况下，一共有多少种数字排列
            if(i < cur) ans += cnt[len - 1];
            else if(i == cur) ans += f2(digits, cnt, num, offset / 10, len - 1);
            else break;
        }
        return ans;
    }
};


class Solution 
{
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) 
    {
        auto s = to_string(n);
        int m = s.size(), memo[m];
        memset(memo, -1, sizeof(memo));
        // is_limit : true，前面所填的数字都和 n 相同
        // is_limit : false，后面所填的数字可以是 digits 中的任意数字
        // is_num : false, 是否是一个合法的数字
        function<int(int, bool, bool)> f = [&](int i, int is_limit, int is_num)
        {
            // is_num 为 ture 表示等到了一个合法数字
            if(i == m) return is_num;
            // 缓存命中
            if(!is_limit && memo[i] != -1) return memo[i];

            int ret = 0;
            if(!is_num)
            {
                // 前面不填数字，那么可以跳过当前数位，也不填数字
                // is_limit 改为 false，因为没有填数字，位数都比 n 要短，自然不会受到 n 的约束
                // is_num 仍然为 false，因为没有填任何数字
                ret = f(i + 1, false, false);
            }
            // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）   
            char up = is_limit ? s[i] : '9';
            // 注意：对于一般的题目而言，如果这里 is_num 为 false，则必须从 1 开始枚举，由于本题 digits 没有 0，所以无需处理这种情况 
            for(auto& d : digits) // 枚举要填入的数字 d
            {
                // d 超过上限，由于 digits 是有序的，后面的 d 都会超过上限，故退出循环
                if(d[0] > up) break; 
                // is_limit：如果当前受到 n 的约束，且填的数字等于上限，那么后面仍然会受到 n 的约束
                // is_num 为 true，因为填了数字
                ret += f(i + 1, is_limit && d[0] == up, true);
            }
            // 在不受到任何约束的情况下，记录结果
            if(!is_limit && is_num) memo[i] = ret; 
            return ret;
        };
        return f(0, true, false);
    }
};